package Leetcode;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class MedianFinder {

    LinkedList<Integer> heap;
    Integer len;

    public MedianFinder() {
        heap = new LinkedList<>();
        len = 0;
    }

    public void addNum(int num) {
        heap.add(num);
        ++len;
    }

    public double findMedian() {
        heap.sort(Comparator.comparingInt(o -> o));
        if (len % 2 == 0){
            int l = len / 2 - 1;
            int r = len / 2;
            double i = (double) heap.get(l) + heap.get(r);
            return i / 2;
        } else {
            return heap.get(len / 2);
        }
    }

}
